package 优先级队列;

import java.util.PriorityQueue;
// 给一组数据流，求出每次添加数据后的中位数。
// 我们用大小根堆来解决问题
// 设置 左大根堆x   右小根堆y
// 然后将放入的数进行比较决定放到哪一根堆里很轻松找到中位数
public class 数据流的中位数 {

    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    public void MedianFinder()
    {
        left = new PriorityQueue<>((a,b)->b-a);// 大根堆
        right = new PriorityQueue<>((a,b)->a-b);// 小根堆
    }
    public void addNum(int num)
    {

        if(left.size() == right.size())
        {
            if(left.isEmpty() || num<= left.peek())
            {
                left.offer(num);
            }
            else{
                right.offer(num);
                left.offer(right.poll());
            }
        }
        else
        {
            if(num<= left.peek())
            {
                left.offer(num);
                right.offer(left.poll());
            }else{
                right.add(num);
                left.offer(right.poll());
            }
        }
    }
    public double findMedian()
    {
        if(left.size() == right.size()) return (left.peek()+ right.peek())/2.0;
        else return left.peek();
    }

    }

